#define _CRT_SECURE_NO_WARNINGS 2
#pragma once
#include<iostream>
#include<vector>

using namespace std;

template<class T>
 struct AVLTreeNode
{

	 AVLTreeNode(T& val)
		 :left_(nullptr)
		 ,right_(nullptr)
		 ,parent_(nullptr)
		 ,bf_(0)
		 ,val_(val)
	 {}


	 AVLTreeNode(const AVLTreeNode<T>& tmp)
		 :left_(tmp.left_)
		 ,right_(tmp.right_)
		 ,parent_(tmp.parent_)
		 ,bf_(tmp.bf_)
		 ,val_(tmp.val_)
	 {}

	 AVLTreeNode<T>* left_;
	 AVLTreeNode<T>* right_;
	 AVLTreeNode<T>* parent_;
	 int bf_;
	 T val_;
};

 template<class T>
 class AVLTree
 {
	 typedef AVLTreeNode<T> Node;

 public:
	 AVLTree()
		 :root_(nullptr)
	 {}

	 ~AVLTree()
	 {}

	 //考虑parent是否为root
	 //考虑parent->left is existed
	 //考虑旋转后相应指针的更新
	 void _RotateL(Node* parent)
	 {
		 Node* pRight = parent->right_;
		 Node* pRightL = pRight->left_;

		 Node* pLeft = parent->left_;
		 parent->right_ = pRightL;
		 if (pRightL)
		 {
			 pRightL->parent_ = parent;
		 }

		 Node* pparent = parent->parent_;
		 pRight->left_ = parent;
		 parent->parent_ = pRight;

		 if (pparent)
		 {
			 if (pparent->left_ == parent)
				 pparent->left_ = pRight;
			 else
				 pparent->right_ = pRight;
			 pRight->parent_ == pparent;
		 }
		 else
		 {
			 root_ = pRight;
			 pRight->parent_ = nullptr;
		 }

		 pRight->bf_ = parent->bf_ = 0;
	 }

	 void _RotateR(Node* parent)
	 {
		 Node* pLeft = parent->left_;
		 Node* pLeftR = pLeft->right_;

		 Node* pRight = parent->right_;
		 parent->left_ = pLeftR;
		 if (pLeftR)
		 {
			 pLeftR->parent_ = parent;
		 }

		 Node* pparent = parent->parent_;
		 pLeft->right_ = parent;
		 parent->parent_ = pLeft;

		 if (pparent)
		 {
			 if (pparent->left_ == parent)
				 pparent->left_ = pLeft;
			 else
				 pparent->right_ = pLeft;
			 pLeft->parent_ = pparent;
		 }
		 else
		 {
			 _root = pLeft;
			 pLeft->parent_ = nullptr;
		 }

		 pRight->bf_ = parent->bf_ = 0;
		 
	 }

	 void _RotateRL(Node* parent)
	 {
		 Node* pRight = parent->right_;
		 Node* pRightL = pRight->left_;
		 int bf = pRightL->bf_;

		 _RotateR(pRight);
		 _Rotate(parent);

		 if (bf == 0)
		 {
			 parent->bf_ = 0;
			 pRight->bf_ = 0;
			 pRightL->bf_ = 0;
		 }
		 if (bf == -1)
		 {
			 parent->bf_ = 0;
			 pRight->bf_ = 1;
			 pRightL->bf_ = 0;
		 }
		 if (bf == 1)
		 {
			 parent->bf_ = -1;
			 pRight->bf_ = 0;
			 pRightL->bf_ = 0;
		 }
	 }

	 void _RotateLR(Node* parent)
	 {
		 Node* pLeft = parent->left_;
		 Node* pLeftR = pLeft->right_;
		 int bf = pLeftR->bf_;

		 _RotateL(pLeft);
		 _RotateR(parent);

		 if (bf == 0)
		 {
			 parent->bf_ = 0;
			 pRight->bf_ = 0;
			 pRightL->bf_ = 0;
		 }
		 if (bf == -1)
		 {
			 parent->bf_ = 1;
			 pRight->bf_ = 0;
			 pRightL->bf_ = 0;
		 }
		 if (bf == 1)
		 {
			 parent->bf_ = 0;
			 pRight->bf_ = 0;
			 pRightL->bf_ = -1;
		 }
	 }

	 bool Insert(const T& val)
	 {
		 if (root_ == nullptr)
		 {
			 root_ = new Node(val);
			 return true;
		 }
		 Node* cur = root_, * parent = root_;
		 while (cur)
		 {
			 if (cur->val_ > val)
			 {
				 parent = cur;
				 cur = cur->left_;
			 }
			 else if (cur->val_ < val)
			 {
				 parent = cur;
				 cur = cur->right_;
			 }
			 else
				 return false;
		 }
		 cur = new Node(val);
		 if (parent->val_ > val)
		 {
			 parent->left_ = newnode;
		 }
		 else
		 {
			 parent->right_ = newnode;
		 }
		
		 while (parent)
		 {
			 if (parent->left_ == cur)
				 parent->bf_--;
			 else
				 parent->bf_++;

			 if (parent->bf_ == 0)
				 break;
			 else if (parent->bf_ == -1 || parent->bf_ == 1)
			 {
				 cur = parent;
				 parent = cur->parent_;
			 }
			 else
			 {
				 if (parent->bf_ == -2 && cur->bf_ == -1)
					 _RotateR(parent);
				 else if (parent->bf_ == -2 && cur->bf_ == 1)
					 _RotateLR(parent);
				 else if (parent->bf_ == 2 && cur->bf_ == 1)
					 _RotateL(parent);
				 else
					 _RotateRL(parent);

				 break;
			 }
		 }
		 return true;
	 }

 private:
	 Node* root_;
 };